﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Net;

namespace NeurOthello.Logic
{
    class Bitboard : Othello
    {
        
        /* 
         * Matris med adjecent(x, y) ^ not(svart(x,y) V vit(x,y) skall kunna ge all möjligen möjliga drag för att snabba upp sökningen.
         * */
        private UInt64 black = 0x0000001008000000UL;
        private UInt64 white = 0x0000000810000000UL;
        private BitboardHash boardHash;

        private int[,] gameboard;
        private double[] inputboard;
        private bool boardChange = true;        

        public override int[,] Gameboard 
        { 
            get 
            {
                if (boardChange)
                {
                    gameboard = ExtractBoard();
                    inputboard = ExtractInputBoard();
                    boardChange = false;
                }
                return gameboard;
            }
        }

        public override double[] Inputboard
        {
            get
            {
                if (boardChange)
                {                    
                    inputboard = ExtractInputBoard();
                    boardChange = false;
                }
                return inputboard;
            }
        }

        private static Hashtable transpositionTable = new Hashtable(20000);
 

              

        private static int[] directionsN = new int[8] { -8, -9, -1, 7, 8, 9, 1, -7 };
        private static UInt64[] directionBorders = new UInt64[4] { 0xFF000000000000FFUL, 0xFF818181818181FFUL, 0x8181818181818181UL, 0xFF818181818181FFUL };
        private static string[] dirLables = new string[8] { "Up", "UpLeft", "Left", "LeftDown", "Down", "DownRight", "Right", "RightUp" };
        private const int Up = 0, UpLeft = 1, Left = 2, LeftDown = 3, Down = 4, DownRight = 5, Right = 6, RightUp = 7; 
        private static UInt64[] positions = new UInt64[64];
        private static UInt64[] diagonals = new UInt64[16];

        private static int[] dirFlipMask = new int[64] {  112, 112, 124, 124, 124, 124, 28, 28,
                                                          112, 112, 124, 124, 124, 124, 28, 28,
                                                          241, 241, 255, 255, 255, 255, 31, 31,
                                                          241, 241, 255, 255, 255, 255, 31, 31,
                                                          241, 241, 255, 255, 255, 255, 31, 31,
                                                          241, 241, 255, 255, 255, 255, 31, 31,
                                                          193, 193, 199, 199, 199, 199, 7,  7,
                                                          193, 193, 199, 199, 199, 199, 7,  7 
                                                          };

        private static int[] adjecentMask = new int[64] { 112, 124, 124, 124, 124, 124, 124, 28,
                                                          241, 255, 255, 255, 255, 255, 255, 31,
                                                          241, 255, 255, 255, 255, 255, 255, 31,
                                                          241, 255, 255, 255, 255, 255, 255, 31,
                                                          241, 255, 255, 255, 255, 255, 255, 31,
                                                          241, 255, 255, 255, 255, 255, 255, 31,
                                                          241, 255, 255, 255, 255, 255, 255, 31,
                                                          193, 199, 199, 199, 199, 199, 199, 7 
                                                          };

        private static int[] index64 = new int[64] {
                                            63,  0, 58,  1, 59, 47, 53,  2,
                                            60, 39, 48, 27, 54, 33, 42,  3,
                                            61, 51, 37, 40, 49, 18, 28, 20,
                                            55, 30, 34, 11, 43, 14, 22,  4,
                                            62, 57, 46, 52, 38, 26, 32, 41,
                                            50, 36, 17, 19, 29, 10, 13, 21,
                                            56, 45, 25, 31, 35, 16,  9, 12,
                                            44, 24, 15,  8, 23,  7,  6,  5
                                            };

        private static UInt64[] adjacency = new UInt64[64];
        private static bool adjacencyInnitiated = false;

        public Bitboard()
        {
            if (!adjacencyInnitiated)
            {
                InnitiateAdjacencyTable();
                adjacencyInnitiated = true;
                DefineDiagonals();
            }
            boardHash = new BitboardHash();
        }

        public Bitboard(Bitboard board)
        {
            if (!adjacencyInnitiated)
            {
                InnitiateAdjacencyTable();                              
                adjacencyInnitiated = true;
                DefineDiagonals();
            }
            
            this.black = board.black;
            this.white = board.white;
            boardHash = new BitboardHash(board.boardHash);
            PlayerTurn = board.PlayerTurn;
            if (!HasMove(PlayerTurn))
                PlayerTurn = 3 - PlayerTurn;            
        }

        
 
/**
 * bitScanForward
 * @author Martin Läuter (1997)
 *         Charles E. Leiserson
 *         Harald Prokop
 *         Keith H. Randall
 * "Using de Bruijn Sequences to Index a 1 in a Computer Word"
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x07EDD5E59A4E28C2);
   assert (bb != 0);
   return index64[((bb & -bb) * debruijn64) >> 58];
}*/
        public static int BitScanFwd(UInt64 board)
        {
            const UInt64 debruijn64 = 0x07EDD5E59A4E28C2UL;
            if (board != 0)
                return index64[((board) * debruijn64) >> 58];
            
            return -1;
            
        }

        public static UInt64 Rotate90(UInt64 board)
        {
            return FlipDiag0088(FlipBoardVertical(board));
        }

        public static UInt64 Rotate180(UInt64 board)
        {
            return MirrorBoardHorizontal(FlipBoardVertical(board));
        }

        public static UInt64 Rotate270(UInt64 board)
        {
            return FlipDiag0880(FlipBoardVertical(board));
        }

        private static UInt64 FlipBoardVertical(UInt64 board)
        {
            return (ulong)IPAddress.HostToNetworkOrder((long)board);
        }

        //mirrorHorizontal     flipDiagA1H8        flipDiagA8H1

        /* kod tagen och anpassad till C# frå chessprogramming.wikispaces.com
         * U64 mirrorHorizontal (U64 x) {
             const U64 k1 = C64(0x5555555555555555);
             const U64 k2 = C64(0x3333333333333333);
             const U64 k4 = C64(0x0f0f0f0f0f0f0f0f);
             x = ((x >> 1) & k1) | ((x & k1) << 1);
             x = ((x >> 2) & k2) | ((x & k2) << 2);
             x = ((x >> 4) & k4) | ((x & k4) << 4);
             return x;
            }*/
        private static UInt64 MirrorBoardHorizontal(UInt64 board)
        {
            const UInt64 k1 = 0x5555555555555555UL;
            const UInt64 k2 = 0x3333333333333333UL;
            const UInt64 k4 = 0x0f0f0f0f0f0f0f0fUL;
            UInt64 mirr = board;
            mirr = ((mirr >> 1) & k1) | ((mirr & k1) << 1);
            mirr = ((mirr >> 2) & k2) | ((mirr & k2) << 2);
            mirr = ((mirr >> 4) & k4) | ((mirr & k4) << 4);
            return mirr;
        }

        /* kod tagen och anpassad till C# frå chessprogramming.wikispaces.com
        U64 flipDiagA1H8(U64 x)
        {
            U64 t;
            const U64 k1 = C64(0x5500550055005500);
            const U64 k2 = C64(0x3333000033330000);
            const U64 k4 = C64(0x0f0f0f0f00000000);
            t = k4 & (x ^ (x << 28));
            x ^= t ^ (t >> 28);
            t = k2 & (x ^ (x << 14));
            x ^= t ^ (t >> 14);
            t = k1 & (x ^ (x << 7));
            x ^= t ^ (t >> 7);
            return x;
        }
        */

        private static UInt64 FlipDiag0088(UInt64 board)
        {
            const UInt64 k1 = 0x5500550055005500UL;
            const UInt64 k2 = 0x3333000033330000UL;
            const UInt64 k4 = 0x0f0f0f0f00000000UL;
            UInt64 mirr = board, t;
            t = k4 & (mirr ^ (mirr << 28));
            mirr ^= t ^ (t >> 28);
            t = k2 & (mirr ^ (mirr << 14));
            mirr ^= t ^ (t >> 14);
            t = k1 & (mirr ^ (mirr << 7));
            mirr ^= t ^ (t >> 7);

            return mirr;  
        }

        /* kod tagen och anpassad till C# frå chessprogramming.wikispaces.com
        U64 flipDiagA8H1(U64 x)
        {
            U64 t;
            const U64 k1 = C64(0xaa00aa00aa00aa00);
            const U64 k2 = C64(0xcccc0000cccc0000);
            const U64 k4 = C64(0xf0f0f0f00f0f0f0f);
            t = x ^ (x << 36);
            x ^= k4 & (t ^ (x >> 36));
            t = k2 & (x ^ (x << 18));
            x ^= t ^ (t >> 18);
            t = k1 & (x ^ (x << 9));
            x ^= t ^ (t >> 9);
            return x;
        }
         */
        private static UInt64 FlipDiag0880(UInt64 board)
        {
            const UInt64 k1 = 0xaa00aa00aa00aa00UL;
            const UInt64 k2 = 0xcccc0000cccc0000UL;
            const UInt64 k4 = 0xf0f0f0f00f0f0f0fUL;
            UInt64 mirr = board, t;
            t = board^(board << 36);
            mirr ^= k4 & (t ^ (mirr >> 36));
            t = k2 & (mirr ^ (mirr << 18));
            mirr ^= t ^ (t >> 18);
            t = k1 & (mirr ^ (mirr << 9));
            mirr ^= t ^ (t >> 9);

            return mirr;            
        }
        
        public override void ResetBoard()
        {
            black = 0x0000001008000000UL;
            white = 0x0000000810000000UL;
            boardHash = new BitboardHash();
            boardChange = true;
        }

        private void InnitiateAdjacencyTable()
        {
            
            UInt64 adj;
            int dirs;
            for (int k = 0; k < 64; k++)
            {
                dirs = adjecentMask[k];
                adj = 0;
                positions[k] = (1UL << k);
                for (int i = 0; i < 8; i++)
                {
                    if (0 != (dirs & (1 << i)))
                        adj |= (1UL << (k + directionsN[i]));
                }
                adjacency[k] = adj;
            }           
        }

        private void UpdateHash(int sqrN, int playerId)
        {
            boardHash.UpdateHash(sqrN, playerId);
        }

        public override void ClearTranspositions() 
        {
            transpositionTable.Clear();
        }

        public override void AddTranspositionValue(double val)
        {
            if(!transpositionTable.ContainsKey(boardHash))
                transpositionTable.Add(boardHash, val);

            BitboardHash temp = boardHash.Rotated90;
            if (!transpositionTable.ContainsKey(temp))
                transpositionTable.Add(temp, val);

            temp = boardHash.Rotated180;
            if (!transpositionTable.ContainsKey(temp))
                transpositionTable.Add(temp, val);

            temp = boardHash.Rotated270;
            if (!transpositionTable.ContainsKey(temp))
                transpositionTable.Add(temp, val);
        }

        public override double FindTranspositionValue()
        {
            if (transpositionTable.ContainsKey(boardHash))
                return (double)transpositionTable[boardHash];
            return NullToken;
        }

        private UInt64 Adjecent(int sqrN)
        {
            return adjacency[sqrN];
        }

        private bool PossibleMove(int i, int playerId)
        {
            if (player1 == playerId)
              return (((black|white) & positions[i]) == 0 && (adjacency[i] & white) != 0);
            return (((black | white) & positions[i]) == 0 && (adjacency[i] & black) != 0);
            
        }

        private UInt64 PossibleMoves()
        {
            UInt64 pos = 0;
            for (int i = 0; i < 64; i++)
                if (PossibleMove(i, 1))
                    pos |= positions[i];
            return pos;
        }

        public int[,] ExtractBoard()
        {
            int[,] arrayBoard = new int[8, 8];
            for (int y = 0; y < 8; y++)
                for (int x = 0; x < 8; x++)
                {
                    arrayBoard[x, y] = GetSquare(XnY2int(x, y));
                }

            return arrayBoard;
        }

        public double[] ExtractInputBoard()
        {
            double[] inputBoard = new double[130];
            for (int i = 0; i < 64; i++)
                if (((black >> i) & 1UL) != 0)
                    inputBoard[i] = 1;
                else inputBoard[i] = 0;

            for (int i = 64; i < 128; i++)
                if (((white >> i) & 1UL) != 0)
                    inputBoard[i] = 1;
                else inputBoard[i] = 0;

            if (PlayerTurn == 0)
            {
                inputBoard[128] = 0.5;
                inputBoard[129] = 0.5;
            }
            else
            {
                inputBoard[128] = 2 - PlayerTurn;
                inputBoard[129] = PlayerTurn - 1;
            }
            return inputBoard;
        }

        public override bool PlaceMarker(int playerId, Position pos)
        {
            return PlaceMarker(playerId, pos.X, pos.Y);
        }

        public override bool PlaceMarker(int playerId, int x, int y)
        {
            int sqrN = XnY2int(x, y);
            if (CheckMove(sqrN, playerId, true))
            {
                SetSquare(sqrN, playerId);

                if (HasMove(Opponent(playerId)))
                    PlayerTurn = Opponent(playerId);
                else if (!HasMove(playerId))
                    PlayerTurn = 0;
                return true;
            }
            return false;
        }

        public override Position[] AllMoves(int playerId)
        {
            List<Position> moves = new List<Position>();
            for (int x = 0; x < 8; x++)
                for (int y = 0; y < 8; y++)
                   
                        if (CheckMove(XnY2int(x, y), playerId, false))
                            moves.Add(new Position(x, y));
            return moves.ToArray();
        }

        public override int CountMoves(int playerId)
        {
            int count = 0;
            UInt64 posMoves = PossibleMoves();
            for (int x = 0; x < 8; x++)
                for (int y = 0; y < 8; y++)
                    
                        if (CheckMove(XnY2int(x, y), playerId, false))
                            count++;
            return count;
        }

        public override bool HasMove(int playerId)
        {
            for (int i = 0; i < 64; i++)
            {                
                    if (CheckMove(i, playerId, false))
                        return true;
            }
            return false;
        }

        public bool CheckMove(int sqrN, int playerId, bool place)
        {
            bool valid = false;
            if (PossibleMove(sqrN, playerId))
            {                
                int dirs = dirFlipMask[sqrN];                
                for (int i = 0; i < 8; i++)
                    if (0 != (dirs & (1 << i)))
                        if (CheckMoveDir(sqrN, i, playerId, place))
                        {
                            valid = true;
                            if (!place)
                                break;
                        }
            }
            return valid;
        }

        public bool CheckMoveDir(int sqrN, int dir, int playerId, bool place)
        {
            int dirShift = directionsN[dir];
            int pos = sqrN + dirShift;
            while (GetSquare(pos, Opponent(playerId)))
            {
                pos += dirShift;
                if (GetSquare(pos, playerId))
                {
                    if (place)
                    {
                        while (pos != sqrN)
                        {
                            SetSquare(pos, playerId);
                            pos -= dirShift;
                        }
                    }
                    return true;
                }

                if (0 != (directionBorders[dir % 4] & (1UL << pos)))
                    break;
            }
            return false;
        }


        public bool GetSquare(int sqrN, int playerId)
        {
            if (sqrN >= nSquares || sqrN < 0)
                return false;
            if (playerId == player1)
                return 0 != (black & positions[sqrN]);
            return 0 != (white & positions[sqrN]);
        }

        public int GetSquare(int sqrN)
        {
            if (sqrN >= nSquares || sqrN < 0)
                return 0;
            if (0 != ((black) & positions[sqrN]))
                return 1;
           // if (0 != (PossibleMoves() & (1UL << sqrN)))
            //    return 1;
           // if (0 != (1UL & (black >> sqrN)))
           //     return 1;
            if (0 != ((white) & positions[sqrN]))
                return 2;
            return 0;
        }

        public bool IsEmpty(int sqrN)
        {
            return (0 == ((white | black) & positions[sqrN]));
        }

        public void SetSquare(int sqrN, int playerId)
        {
            boardChange = true;
            if (playerId == 0)
            {
                if (GetSquare(sqrN, 1))
                {
                    black ^= positions[sqrN];
                    UpdateHash(sqrN, 1);
                }
                if (GetSquare(sqrN, 2))
                {
                    white ^= positions[sqrN];
                    UpdateHash(sqrN, 2);
                }
                return;
            }
            else if (playerId == player1)
            {
                black |= positions[sqrN];
                UpdateHash(sqrN, playerId);
                if (GetSquare(sqrN, Opponent(playerId)))
                {
                    white ^= positions[sqrN];
                    UpdateHash(sqrN, Opponent(playerId));
                }
                return;
            }
            else
            {
                white |= positions[sqrN];
                UpdateHash(sqrN, playerId);
                if (GetSquare(sqrN, Opponent(playerId)))
                {
                    black ^= positions[sqrN];
                    UpdateHash(sqrN, Opponent(playerId));
                }
            }
        }

        public override void SetSquare(int x, int y, int playerId)
        {
            SetSquare(XnY2int(x, y), playerId);
        }

        public int XnY2int(int x, int y)
        {
            return (y) * 8 + x;
        }

        public override void boardCount(ref int b, ref int w, ref int u)
        {
            UInt64 tB = black, tW = white;
            while (tB != 0)
            {
                b++;
                tB &= (tB - 1);
            }
            while (tW != 0)
            {
                w++;
                tW &= (tW - 1);
            }
            u = 64 - b - w;
        }

     
        public override int SafeScore(int playerId)
        {
            UInt64 playerBoard;
            int score = 0;
            if (playerId == 1)
                playerBoard = black;
            else
                playerBoard = white;

            for (int i = 0; i < 16; i += 4)
            {
                if ((diagonals[i] & playerBoard) != 0)
                {
                    score += 5;
                    if ((diagonals[i + 1] & playerBoard) == diagonals[i + 1])
                    {
                        score += 2;
                        if ((diagonals[i + 2] & playerBoard) == diagonals[i + 2])
                        {
                            score += 3;
                            if ((diagonals[i + 3] & playerBoard) == diagonals[i + 3])
                                score += 4;
                        }
                    }
                }
            }
            return score;
        }



        private void DefineDiagonals()
        {
            diagonals[0] = 0x8000000000000000UL;
            int start = BitScanFwd(diagonals[0]);
            int horDir = -1;
            int vertDir = -8;
            diagonals[1] = 0 | positions[start + horDir] | positions[start + vertDir];
            diagonals[2] = 0 | positions[start + horDir + horDir] | positions[start + horDir + vertDir] | positions[start + vertDir + vertDir];
            diagonals[3] = 0 | positions[start + horDir + horDir + horDir] | positions[start + horDir + horDir + vertDir] | positions[start + vertDir + vertDir + vertDir] | positions[start + vertDir + vertDir + horDir];
            
            for (int i = 4; i < 16; i++)
            {
                diagonals[i] = Rotate90(diagonals[i - 4]);
            }
        }

        public static int Opponent(int playerId)
        {
            return 3 - playerId;
        }




    }
}
